---
title: "AB路线"
created: 2025-11-28
tags:
  - 算法
---

# AB路线

## 题目 [AB路线](https://www.lanqiao.cn/problems/17109/learning/)

![[image-15fac6c3.png]]

## 思路分析

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

//bfs 多了一个限制条件 计数器 计数器未达k时 得一直走相同的格子 计数器达到k时 只能走不同的格子

typedef pair<int,int> PII;

typedef pair<PII,int> PPI;

const int N=1010;

char g[N][N];

int n,m,k;

int dist[N][N];

int dx[]={-1,0,1,0};

int dy[]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && dist[x][y]==-1;

}

void bfs(int x,int y,int step){

	memset(dist,-1,sizeof dist);

	queue<PPI> q;

	q.push({{x,y},step});

	dist[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first.first,uy=cur.first.second,ut=cur.second;

		if(ux==n && uy==m){

			cout<<dist[n][m]<<endl;

			return;

		}

		//当前是第ut步 若ut%k==0 说明下一步要拓展不同的 否则下一步还是走相同的

		char nc=g[ux][uy];

		if (ut % k == 0) {

            nc = (nc == 'A') ? 'B' : 'A';

        }

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==nc){

				dist[nx][ny]=dist[ux][uy]+1;

				q.push({{nx,ny},ut+1});

			}

		}

	}

	cout<<-1<<endl;

	return;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m>>k;

	string tmp;

	getline(cin,tmp);

	for(int i=1;i<=n;i++){

		getline(cin,tmp);

		for(int k=0,j=1;k<tmp.size();k++){

			if(tmp[k]!=' ')

				g[i][j++]=tmp[k];

		}

	}

//	for(int i=1;i<=n;i++){

//		for(int j=1;j<=m;j++){

//			cout<<g[i][j]<<" ";

//		}

//		cout<<endl;

//	}

	bfs(1,1,1);

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[删边问题|删边问题]] 🏠 [[00-冲刺国赛]] ➡️ [[抓娃娃|抓娃娃]]